Multi-tenant data stores are used in environments where multiple entities store and/or manage their data in a common repository. These may be used, for example, in cloud storage applications, e-commerce platforms (e.g., “virtual storefronts”), online service providers, resource management services, and other situations. To maintain data consistency, such systems may rely on updates from tenants being processed in the order they were received. However, in many instances, the chance of out of order messages being received at various nodes in the system increases as database size and complexity increases, requiring additional processing or other safeguards to ensure that the eventual state of the data store is consistent and correct.